#include "lru.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * 函数：模拟LRU页面置换算法。
 *
 * @param queue_frames 一个字符串，表示页面访问序列。
 *                     字符串中的每个字符是一个数字，表示一个页面号。
 * @param num_frames   页框的数量，表示物理内存中可用的页框数。
 */

// typedef struct
// {
//   int ram_pos;
//   int ppn;
//   memNode* prev;
//   memNode* next;

// } memNode;


void
lru_page_replacement (char *queue_frames, int num)
{
  // TODO
  int frames[num];
  int access_count[num];

  // Initialize page frames to be -1
  // and frame count to be  0
  for (int i = 0; i < num; ++i) 
  {
      frames[i] = -1;
      access_count[num - i - 1] = i;
  }

  char *token = strtok(queue_frames, ",");
  int last_page = -1;
  while (token != NULL) 
  {
      int page = atoi(token);
      int found = -1;
      
      for (int i = 0; i < num; ++i) 
      {
          if (frames[i] == page) {
              found = i;
          }
      }
      
      if (found == -1) // need eviction
      {
        // find LRU page to evict
        int lru = 0;
        for (int i = 0; i < num; ++i) 
        {
            if (access_count[i] > access_count[lru]) {
              lru = i;
            }
        }
        // evict lru and make the new page resident in the mem pos
        frames[lru] = page;
        found = lru;
      }

      if(last_page != page)
      {
        for (int i = 0; i < num; ++i)
        {
          ++access_count[i];
        }
      }

      // make the newly accessed page count = 0
      access_count[found] = 0;

      
      // print current frames
      printf("Access:%d,Frames: [", page);
      for (int i = 0; i < num; ++i) 
      {
          if (i > 0) printf(",");
          printf("%d", frames[i]);
      }
      printf("]\n");

      last_page = page;
      
      token = strtok(NULL, ",");
  }
}
